class Solution:
    '''
    该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包的方法来求解。
    可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：
                      sum(P) - sum(N) = target
    sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
                    2 * sum(P) = target + sum(nums
    '''
    def findTargetSumWays(self, nums, s):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        sums = sum(nums)
        if sums < s or (sums + s) % 2 == 1:
            return 0
        t = int((sums + s) / 2)

        f = [0] * (t + 1)

        f[0] = 1

        for i in range(1, n + 1):
            for j in range(t, -1, -1):
                if j >= nums[i - 1]:
                    f[j] = f[j] + f[j - nums[i - 1]]
        return f[-1]